package com.lwg.datastructure.dynamicPrograming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @FileName: ClimbStairs.java
 * @Description: 爬楼梯
 * Copyright: Copyright(C) 2020-2022
 * Company  : Sunyard.hangzhou
 * @author: 李炜光
 * @slogan:
 * @Date: 2022/2/16 0016
 * <p>
 * <p>
 * 1级台阶(一种方法)
 * 2级台阶(爬一级台阶或两级台阶  两种方法)
 * n级台阶(从n-1级台阶爬1个台阶，从n-2级台阶爬2个台阶)
 * 公式 f(n)=f(n-1)+f(n-2);
 * <p>
 * 菲波那切公式
 * <p>
 * double sqrt5 = Math.sqrt(5);
 * double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
 * return (int) Math.round(fibn / sqrt5);
 */

public class ClimbStairs {
    //爬楼梯
    public int climbStairs(int n) {
        /*if (n < 4) {
            return n;
        }
        int dp[] = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 3; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];*/

        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    //使用最小花费爬楼梯  方法一
    /*public int minCostClimbingStairs(int[] cost) {
        //台阶的长度
        int n = cost.length;
        //1. 可以从下标为0和下标为1的台阶开始爬楼梯
        // 例如dp[i] 表示从0/1 的台阶爬到第i级台阶 所花费的金额
        int dp[] = new int[n+1];
        //当2<=i<=n时  有两种方式达到第i级台阶，一为从i-1级台阶 花费cost[i-1] 金额到达i, 二为从i-2级台阶，花费cost[i-2] 金额到达i
        for (int i = 2; i <= n; i++) {
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }*/

    //优化 dp[i]只与dp[i-1]和dp[i-2] 有关，所以可以使用滚动法  方法二
    //使用最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        //台阶的长度
        int n = cost.length;
        //1. 可以从下标为0和下标为1的台阶开始爬楼梯
        //当2<=i<=n时  有两种方式达到第i级台阶，一为从i-1级台阶 花费cost[i-1] 金额到达i, 二为从i-2级台阶，花费cost[i-2] 金额到达i
        int pre = 0, curr = 0, after = 0;
        for (int i = 2; i <= n; i++) {
            after = Math.min(curr + cost[i - 1], pre + cost[i - 2]);
            pre = curr;
            curr = after;
        }
        return after;
    }
}

class MainClass6 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int n = Integer.parseInt(line);

            int ret = new ClimbStairs().climbStairs(n);

            String out = String.valueOf(ret);

            System.out.print(out);
        }
    }
}

class MainClass7 {
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for (int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int[] cost = stringToIntegerArray(line);

            int ret = new ClimbStairs().minCostClimbingStairs(cost);

            String out = String.valueOf(ret);

            System.out.print(out);
        }
    }
}